package main.Q101_200;

import java.util.*;

public class Q121_130 {
    public static void main(String[] args) {
        System.out.println("Question121：买卖股票的最佳时机");
        System.out.println("Question122：买卖股票的最佳时机Ⅱ");
        System.out.println("Question123：买卖股票的最佳时机Ⅲ");
        System.out.println("Question124：二叉树的" +
                "最大路径和");
        System.out.println("Question125：验证回文串");
        System.out.println("Question126：");
        System.out.println("Question127：单词接龙");
        System.out.println("Question128：最长连续序列");
        System.out.println("Question129：求根节点到叶节点数字之和");
        System.out.println("Question130：被围绕的区域");
    }
}

class Question121 {
    public int maxProfit(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

class Question122 {
    public static int maxProfit(int[] prices) {
        int total = 0, left = 0, right = 0;
        while (right < prices.length) {
            if (right + 1 < prices.length && prices[right + 1] <= prices[right]) {//没有严格递增
                total = total + prices[right] - prices[left];//将严格上升区间差值相加
                left = right + 1;
                right = left;
            } else if (right + 1 < prices.length && prices[right + 1] > prices[right]) right++;//严格递增
            if (right == prices.length - 1) {
                total = total + prices[right] - prices[left];
                break;
            }
        }
        return total;
    }
}

class Question123 {
    public int maxProfit(int[] prices) {
        int firstBuy = Integer.MIN_VALUE, firstSell = 0, secondBuy = Integer.MIN_VALUE, secondSell = 0;
        for (int price : prices) {
            firstBuy = Math.max(firstBuy, -price);
            firstSell = Math.max(firstSell, price + firstBuy);
            secondBuy = Math.max(secondBuy, firstSell - price);
            secondSell = Math.max(secondSell, price + secondBuy);
        }
        return Math.max(firstSell, secondSell);
    }
}

class Question124 {
    int maxSum = Integer.MIN_VALUE;

    public int process(TreeNode root) {
        if (root == null) return 0;
        int left = process(root.left);
        int right = process(root.right);
        maxSum = Math.max(maxSum, left + root.val + right);//过根节点的可能最大值
        int pathSum = root.val + Math.max(Math.max(0, left), right);//不过根节点或不过子树的可能最大值
        return pathSum < 0 ? 0 : pathSum;
    }

    public int maxPathSum(TreeNode root) {
        process(root);
        return maxSum;
    }

}

class Question125 {
    public static boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        return sgood.toString().equals(sgood_rev.toString());
    }
}

class Question127 {
    Map<String, Integer> wordId = new HashMap<String, Integer>();
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            process1(word);
        }
        process1(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(beginId);
        while (!que.isEmpty()) {
            int x = que.poll();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int it : edge.get(x)) {
                if (dis[it] == Integer.MAX_VALUE) {
                    dis[it] = dis[x] + 1;
                    que.offer(it);
                }
            }
        }
        return 0;
    }

    public void process1(String word) {
        process2(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            process2(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void process2(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
}

class Question128 {
    public static int longestConsecutive(int[] nums) {
        int max = 0;
        int[] dp = new int[nums.length];
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) dp[i] = 1;
            else {
                if (nums[i] - nums[i - 1] == 1) dp[i] = dp[i - 1] + 1;
                else if (nums[i] == nums[i - 1]) dp[i] = dp[i - 1];
                else dp[i] = 1;
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

class Question129 {
    List<Integer> list = new ArrayList<>();

    public void process(TreeNode root, int preNum) {
        if (root == null) {
            list.add(preNum);//将已经组成的数字串加入list中
            return;
        }
        int curNum = preNum * 10 + root.val;//当前节点组成的数
        if (root.left == null && root.right == null) {//当为叶子节点时
            list.add(curNum);
            return;
        }
        if (root.left != null) {
            process(root.left, curNum);
        }
        if (root.right != null) {
            process(root.right, curNum);//组合右孩子
        }
    }

    public int sumNumbers(TreeNode root) {
        int sum = 0;
        process(root, 0);
        if (list.size() != 0) {
            for (Integer i : list) sum += i;
        }
        return sum;
    }
}

class Question130 {
    public void process(char[][] board, char[][] temp, int r, int c) {
        int row = board.length, col = board[0].length;
        board[r][c] = 'O';
        temp[r][c] = 'X';
        if (r - 1 >= 0 && temp[r - 1][c] == 'O') process(board, temp, r - 1, c);//上
        if (r + 1 < row && temp[r + 1][c] == 'O') process(board, temp, r + 1, c);//下
        if (c - 1 >= 0 && temp[r][c - 1] == 'O') process(board, temp, r, c - 1);//左
        if (c + 1 < col && temp[r][c + 1] == 'O') process(board, temp, r, c + 1);//右
    }

    public void solve(char[][] board) {
        int row = board.length, col = board[0].length;
        char[][] temp = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                temp[i][j] = board[i][j];
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        for (int i = 0; i < row; i++) {//左列
            if (temp[i][0] == 'O') {
                process(board, temp, i, 0);
            }
        }
        for (int i = 0; i < row; i++) {//右列
            if (temp[i][col - 1] == 'O') {
                process(board, temp, i, col - 1);
            }
        }
        for (int i = 0; i < col; i++) {//上行
            if (temp[0][i] == 'O') {
                process(board, temp, 0, i);
            }
        }
        for (int i = 0; i < col; i++) {//下行
            if (temp[row - 1][i] == 'O') {
                process(board, temp, row - 1, i);
            }
        }
    }
}